/**
 * @param {number} n
 * @param {number[][]} rides
 * @return {number}
 */
 var maxTaxiEarnings = function(n, rides) {
  const map = new Map()
  for(const [x, y, t] of rides) {
    if(!map.has(x)){
      map.set(x, [])
    }
    map.get(x).push([y, t])
  }  
  const arr = new Array(n+1).fill(0)
  let ans = 0
  const dfs = (s, total) => {
    ans = Math.max(ans, total)
    for(let i = s; i<=n; i++){
      if(map.has(i)){
        for(const [e, t] of map.get(i)){
          const now = total+t+(e-i)
          if(now >= arr[e]){
            dfs(e, now)
            arr[e] = now
          }
        }
      }
    } 
  }
  dfs(1, 0)
  return ans
};
